package com.search;

import java.util.ArrayList;
import java.util.List;

public class Permute {
	static int flag[];
	static int cahe[];
	static List<List<Integer>> list = null;
	public static void main(String[] args) {
		int[] a = new int[] {1,2,3};
		List<List<Integer>> b = permute(a);
		System.out.println(b);
	}
	public static List<List<Integer>> permute(int[] nums) {
        list = new ArrayList();
        flag = new int[nums.length];
        cahe = new int[nums.length];
        permute(nums,0);
        return list;
	}
	public static void permute(int[] nums,int deepth) {
		if(deepth == nums.length) {
			List<Integer> temp = new ArrayList();
			for(int i = 0;i < nums.length;i++) {
				temp.add(cahe[i]);
			}
			list.add(temp);
			return;
		}
		for(int i = 0;i < nums.length;i++) {
			if(flag[i] == 0) {
				flag[i] = 1;
				cahe[deepth] = nums[i];
				permute(nums,deepth + 1);
				flag[i] = 0;
			}
		}
	}
}